/*
 * worst-case: O(n^2)
 * incremental design
 */
void
insertion_sort(int *arr, int n)
{
	int i, j, key;
	for(j=1; j<n; j++) {
		key = arr[j];
		i = j-1;
		while(arr[i]>key && i>=0) {
			arr[i+1] = arr[i];
			i--;
		}
		arr[i+1] = key;
	}
}

void 
insertion_sort_recursive(int *arr, int n)
{
	int i, key;
	if(n <= 1)
		return;
	insertion_sort_recursive(arr, n-1);
	key = arr[n-1];
	i = n-2;
	while(arr[i]>key && i>=0) {
		arr[i+1] = arr[i];
		i--;
	}
	arr[i+1] = key;
}
